package gold.digger;

/**
 * Created by fanzhenyu02 on 2020/3/1.
 */
public class LC35 {

    public int searchInsert(int[] nums, int target) {
        return searchInsertRecur(nums, 0, nums.length - 1, target);
    }

    public int searchInsertRecur(int[] arr, int lb, int ub, int target) {
        if (lb > ub) {
            //cannot find it
            return lb;
        }

        int mid = (lb + ub) / 2;
        if (arr[mid] == target) {
            return mid;
        }

        if (arr[mid] > target) {
            return searchInsertRecur(arr, lb, mid - 1, target);
        } else {
            return searchInsertRecur(arr, mid + 1, ub, target);
        }
    }

    public static void main(String[] args) {
        LC35 an = new LC35();
        int arr[] = {1, 3, 5, 6};
        System.out.println(an.searchInsert(arr, 7));
    }
}
